Queries are used to retrieve sets of data that match certain criteria. For example, a query could be used to retrieve from a data base a set of data for every person born in California AND living in California.
A bitmap index provides an efficient and fast means of retrieving data from a database. A bitmap index is an index that includes a set of bitmaps that can be used to access data. In the context of bitmap indexes, a bitmap is a series of bits that indicate which of the records stored in the body of data satisfy a particular criteria. Each record in the body of data has a corresponding bit in the bitmap. Each bit in the bitmap serves as a flag to indicate whether the record that corresponds to the bit satisfies the criteria associated with the bitmap.
Typically, the criteria associated with a bitmap is whether the corresponding records contain a particular key value. In the bitmap for a given key value, all records that contain the key value will have their corresponding bits set to 1 while all other bits are set to 0. A collection of bitmaps for the key values that occur in the data records can be used to index the data records. In order to retrieve the data records with a given key value, the bitmap for that key value is retrieved from the index and, for each bit set to 1 in the bitmap, the corresponding data record is retrieved. The records that correspond to bits are located based on a mapping function between bit positions and data records.
When retrieving data using a bitmap index, several logical retrieval conditions may be combined using Boolean operations on the appropriate bitmaps. For example, if the data that is to be retrieved is subject to the conditions that key1=&lt;val1&gt; and key2=&lt;val2&gt; and key3=&lt;val3&gt;, a bitwise AND of the bitmaps for key values &lt;val1&gt; and &lt;val2&gt; and val3 can be performed to generate a bitmap that indicates the data items that match all three condition.
Unfortunately, conventional processing of Boolean operations like those above is wasteful. The whole bitmap of a key value is ANDed with the whole bitmaps of the other key values to produce the results. This wastefulness is compounded by the overhead incurred in retrieving the entire bitmaps from disk.
Conventional processing ignores inherent attributes of bitmap indexes that can be exploited for efficiency. For example, bitmaps often contain sequences of zeros. Such sequences are referred to herein as gaps. In a large database system, the gaps found in bitmap indexes are often large. An AND operation may be performed between, for example, four bitmaps. The first bitmap may contain a large gap. In order to determine the AND result corresponding to the gap, the three equally large portions of the last three bitmaps corresponding to the gap can be ignored. The last three can be ignored because the result of ANDing with zeros is always zeros. Thus ANDing whole bitmaps with whole bitmaps, when portions of many of the bitmaps can be ignored, creates unnecessary work for the computer system.
Based on the foregoing, it is clearly desirable to a provide a database system that performs logical operations on bitmaps indexes more efficiently than conventional means of performing logical operations on bitmap indexes.